【算法导论】贪心算法之活动安排问题

​ 对于许多最优化问题来说，采用动态规划来求解最优解有点大材小用了，只需要采用更简单有效的贪心算法就行了。贪心算法就是所做的每一步选择都是当前最佳的，通过局部最佳来寻求全局最佳解。就像砝码称重一样，总是优先选择大的砝码。

​ 贪心算法对大多数优化问题来说能产生最优解，但也不一定总是这样的。能用贪心算法解的典型问题包括活动选择问题、最小生成树、最短路径问题等等。下面我们来讨论活动活动选择问题：

​ 对于上面问题，贪心算法的思想就是：贪心选择使得剩下的、未调度的时间最大化。在本例中，先选择$i=1$,然后从$x_i\ge x_1$的集合中选择$f_i$最小的，此时$i=4$,然后从$x\ge x_4$的集合中选择$f_i$最小的，此时$i=8$,然后从$x\ge x_8$的集合中选择$f_i$最小的，此时$i=11$.因此就可以得到问题的一个最优解。

具体程序实现如下：

#include<stdio.h>
# define N 11

void GreadyActivitySelector(int *s,int *f,int *A,int n);
void RecursiveActivitySelector(int *s,int *f,int *A,int i,int n,int k);

void main()
{
	int s[N]={1,3,0,5,3,5,6,8,8,2,12};//开始时间
	int f[N]={4,5,6,7,8,9,10,11,12,13,14};//结束时间
	int A[N]={0};//初始化
	int n=N;
	GreadyActivitySelector(s,f,A,n);//迭代版本
//	RecursiveActivitySelector(s,f,A,0,n,0);//递归版本
	for(int i=0;i<n;i++)
		printf("%d ",A[i]);//被选择的活动 
}

/****************************************************\
函数功能：选择最佳的活动安排
输入：    各个活动的起始时间和结束时间、待存储被选择活动的数组A、活动个数
输出：    无
\****************************************************/

void GreadyActivitySelector(int *s,int *f,int *A,int n)//迭代版本
{
	A[0]=1;
	int	i=0;
	int j=1;
	for(int m=1;m<n;m++)
	{
		if(s[m]>=f[i])//开始时间大于上个活动的结束时间
		{
			i=m;
			A[j]=m+1;//注意下标与第几位差一
			j++;
		}
	}
}

/****************************************************\
函数功能：选择最佳的活动安排
输入：    各个活动的起始时间和结束时间、待存储被选择活动的数组A、i,n表示子问题的活动，活动个数
输出：    无
\****************************************************/
void RecursiveActivitySelector(int *s,int *f,int *A,int i,int n,int k)//递归版本
{
	int j=k;
	int m=i;

	while((m<n)&&(s[m]<f[i])&&(m!=0))//找到结束时间大于上个活动开始时间的活动
		m=m+1;
	if(m<n)
	{
		A[j]=m+1;//将被选择的活动存储起来
		
		j++;
		RecursiveActivitySelector(s,f,A,m+1,n,j);
	}


}